/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-07
 * Time: 23:15
 */
public class Solution {
    public int index;//记录匹配到的字符串的下标
    public int length;//记录字符串的长度
    public int row;
    public int col;
    public Boolean dfs(char[][] board,String word,int i,int j,int[][] mark){
        //越界了
        if(i<0||i>=row||j<0||j>=col||mark[i][j]==1){
            return false;
        }
        //不匹配直接返回
        if(board[i][j]!=word.charAt(index)){
            return false;
        }
        //匹配上了
        if(index==this.length-1){
            //匹配完了
            return true;
        }
        //没有匹配完继续
        index++;
        mark[i][j]=1;//标记为已经访问,防止该分支上重复访问同一个位置
        Boolean up=dfs(board,word,i-1,j,mark);//上
        Boolean down=dfs(board,word,i+1,j,mark);//下
        Boolean left=dfs(board,word,i,j-1,mark);//左
        Boolean right=dfs(board,word,i,j+1,mark);//右
        if(!up&&!down&&!left&&!right){
            //四个面都没有找到结果
            index--;//注意在这条分支上没有找到结果要及时index--
            mark[i][j]=0;//同时记住重新标记为没有走过
            return false;
        }
        return true;
    }

    public boolean exist(char[][] board, String word) {
        this.row=board.length;
        this.col=board[0].length;
        this.length=word.length();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]==word.charAt(0)){
                    int[][] mark=new int[row][col];//每次匹配mark都要是新的
                    if(dfs(board,word,i,j,mark)){
                        //只要有一个成功就行
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
